package leet.ku._104;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {
	
	class TreeNodePair {
		int depth;
		TreeNode node;
		
		TreeNodePair(int d, TreeNode n) {
			depth = d;
			node = n;
		}
	}
	
	public int maxDepth(TreeNode root) {
		if (root == null)
			return 0;
		
		int result = 0;
		
		Queue<TreeNodePair> queue = new LinkedList<TreeNodePair>();
		queue.add(new TreeNodePair(1, root));
		while (!queue.isEmpty()) {
			TreeNodePair now = queue.poll();
			if (now.depth > result)
				result = now.depth;
			if (now.node.left != null)
				queue.add(new TreeNodePair(now.depth + 1, now.node.left));
			if (now.node.right != null)
				queue.add(new TreeNodePair(now.depth + 1, now.node.right));
		}
		
		return result;
	}
}